#!/usr/env/bin python
# -*- coding: utf-8 -*-

# @Time    : 2020-07-25 9:22 上午
# @Author  : yangdy
# @File    : my_methods
# @Software: PyCharmCE
from functools import lru_cache
from typing import List


def list_display(_list_a):
    for _item_i, _item in enumerate(_list_a):
        print(_item_i, _item)


def work(questions, func, *args, **kwargs):
    for qi, q in enumerate(questions):
        print(f'#{qi}:', q)
        print('ans:', func(q))


def mk_tree(data, TreeNode):
    root = None
    if not data:
        return root
    print('data:', data)
    ld = len(data)
    root = TreeNode(data[0])
    i = 1
    que = [root]
    while que and i < len(data):
        new_que = []
        for x in que:
            left = TreeNode(data[i]) if i < ld and data[i] else None
            i += 1
            x.left = left
            if left:
                new_que.append(left)
            if i < ld:
                right = TreeNode(data[i]) if data[i] else None
                i += 1
                x.right = right
                if right:
                    new_que.append(right)
        que = new_que

    return root


def display(root):
    print('----')

    def _display(rt, dep=0):
        if not rt:
            return
        _display(rt.right, dep+1)
        print(' '*dep, rt.val)
        _display(rt.left, dep+1)
    _display(root)
    print('----')


class Heap:
    def __init__(self, data=None, key=None, reverse=False):
        self.data = data if data is not None else []
        self.key = key
        self.reverse = reverse
        if len(self.data) > 0:
            for i in range(len(self.data)//2, len(self.data)):
                self.down(i)

    def _cmp(self, x, y):
        if self.key:
            x, y = self.key(x), self.key(y)
        return x < y if not self.reverse else x > y

    def clear(self):
        self.data = []

    def down(self, index=0):
        if index * 2 + 1 >= len(self.data):
            return
        x, y, ll = index * 2 + 1, index * 2 + 2, len(self.data)
        u = x if y >= ll or self._cmp(self.data[y], self.data[x]) else y
        if self._cmp(self.data[index], self.data[u]):
            self.data[u], self.data[index] = self.data[index], self.data[u]
            self.down(u)

    def up(self, index=0):
        if index <= 0:
            return
        x = index // 2
        if self._cmp(self.data[x], self.data[index]):
            self.data[x], self.data[index] = self.data[index], self.data[x]
            self.up(x)

    def top(self):
        return self.data[0] if len(self.data) > 0 else None

    def is_empty(self):
        return len(self.data) <= 0

    def insert(self, x):
        self.data.append(x)
        self.up(len(self.data)-1)

    def pop(self):
        if self.is_empty():
            return
        ans = self.data[0]
        last = self.data.pop()
        if not self.is_empty():
            self.data[0] = last
            self.down()
        return ans

